<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <title>单向链表-方法封装</title>
</head>
<body>
  <script src="https://cdn.bootcss.com/lodash.js/4.17.15/lodash.core.min.js"></script>
  <script>
    // 指针 === 引用
    // 链表：包含头指针和节点（data和指针组成）
    function LinkList () {
      this.length = 0; // 链表初始长度
      this.head = null; // 头指针
    }

    // 1. append()
    LinkList.prototype.append = function (data) {
      // 1. 加进来的节点信息
      const currNode = {
        data, // // 当前节点数据
        next: null, // 尾指针
      }
      // 2. 为空时，头指针指向第一个加进来的节点
      if (!this.length) {
        this.head = currNode;
        // 2.1 插入节点后，长度+1
        this.length ++;
        return false;
      }
      // 3. 判断链表长度
      if (this.length) {
        let current = this.head;
        // 3.1 next指针不为空时，将current指向下一个节点
        while (current.next) {
          current = current.next;
        }
        // 3.2 找到链表的最后一个指针为null，标示找到了最后一个节点
        current.next = currNode;
        // 3.3 插入节点后，长度+1
        this.length ++;
      }
    }

    // 2. toString()，将节点的data转换为字符串
    LinkList.prototype.toString = function () {
      let current = this.head, dataStr = '';
      while (current) {
        // 如果是对象
        if (_.isObject(current.data)) {
          current.data = JSON.stringify(current.data);
        }
        dataStr += current.data;
        current = current.next;
      }
      return dataStr;
    }

    // 3. insert()，根据position（索引值）去定位节点，然后插入
    // case1: position < 0 || position > this.length，直接阻止掉
    // case2: position为0,head指针直接指向当前节点
    // case3: 0 < position <= this.length,进行插入操作
    LinkList.prototype.insert = function (data, position) {
      // 1. 当前节点信息
      const currNode = {
        data,
        next: null,
      }
      // 2. case1
      if (position < 0 || position > this.length) return false;
      // 3. case2
      if (position === 0) {
        currNode.next = this.head;
        this.head = currNode;
        this.length ++;
        return false;
      }
      // 4. case3
      let index = 0, preNode = null, current = this.head;
      while (index < position) {
        // 4.1 保存上一个节点（preNode和current的赋值顺序不能颠倒 ，因为需要先将当前节点保存为上一个节点，再把当前节点指向下一个节点）
        preNode = current;
        // 4.2 保存当前节点
        current = current.next;
        // 4.3 索引值+1
        index ++;
      }
      // 4.4 插入节点
      currNode.next = current;
      preNode.next = currNode;
      // 5. 插入后长度+1（不能忘了）
      this.length ++;
    }

    // 4. get()，根据position获取对应节点的data
    LinkList.prototype.get = function (position) {
      let current = this.head, index = 0;
      if (position < 0 || position >= this.length) return undefined;
      while (index < position) {
        current = current.next;
        index ++;
      }
      return current.data;
    }

    // 5. indexOf(),根据节点data值获取索引
    LinkList.prototype.indexOf = function (data) {
      let current = this.head, index = 0;
      // 1. 判断current是否存在
      while (current) {
        const isEqual = _.isEqual(current.data, data); // 通过深比较，判断两个值是否相等
        if (isEqual) {
          // 1.1 相等，返回index
          return index;
        }
        // 不相等，继续向后查找并且index+1
        current = current.next;
        index ++;
      }
      // 不存在或者找不到与data相等的值，返回-1
      return -1;
    }

    // 6. update()
    LinkList.prototype.update = function (position, newData) {
      // 越界判断
      if (position < 0 || position >= this.length) return false;
      let current = this.head, index = 0;
      while (index < position) {
        current = current.next;
        index ++;
      }
      // 对节点进行替换数据
      current.data = newData;
    }

    // 7. removeAt()， 根据position删除对应的节点
    LinkList.prototype.removeAt = function (position) {
      // 越界判断
      if (position < 0 || position >= this.length) return false;
      // 当移除的是第1个节点，将head指针指向head的下一个节点
      if (position === 0) {
        this.head = this.head.next;
        this.length --;
        return false;
      };
      // 移除的不是第一个节点
      let current = this.head, index = 0, preNode = null;
      while (index < position) {
        preNode = current;
        current = current.next;
        index ++;
      }
      // 删除指定节点，将指针指向删除节点的下一个节点
      preNode.next = current.next;
      this.length --;
    }

    // 8. remove()，根据传进来的data，删除对应的节点
    LinkList.prototype.remove = function (data) {
      // 先找到对应的index
      const index = this.indexOf(data);
      // 根据index删除对应的节点
      this.removeAt(index);
    }

    // 9. isEmpty()
    LinkList.prototype.isEmpty = function () {
      return this.length === 0;
    }

    // 10. size(),获取链表的长度
    LinkList.prototype.size = function () {
      return this.length;
    }

    const linkList = new LinkList();
    linkList.append(1);
    linkList.append('cs');
    linkList.append(3);
    console.log(linkList.toString());
    linkList.insert('insert2', 3);
    linkList.insert('insert0', 0);
    console.log(linkList.toString());
    console.log('get', linkList.get(2));
    console.log('get', linkList.get(4));
    console.log('indexOf', linkList.indexOf('cs'));
    console.log('indexOf', linkList.indexOf('insert2'));
    linkList.update(1, {a: 1});
    linkList.update(3, [3, {a: 3}]);
    console.log('update', linkList.toString());
    linkList.removeAt(3);
    console.log('removeAt', linkList.toString());
    linkList.remove(JSON.stringify({a: 1}));
    console.log('remove', linkList.toString());
    console.log('isEmpty', linkList.isEmpty());
    console.log('size', linkList.size());
  </script>
</body>
</html>